package random;

import java.util.ArrayList;
import java.util.LinkedList;

/**
 * 合并两个有序链表
 *
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 *
 * 提示：
 * 两个链表的节点数目范围是 [0, 50]
 * -100 <= Node.val <= 100
 * l1 和 l2 均按 非递减顺序 排列
 */

public class L21 {

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

    public static void main(String[] args) {
        ListNode l1 = buildList(new int[]{1,2,3});
        ListNode l2 = buildList(new int[]{1,3,4});
        ListNode listNode = mergeTwoLists2(l1, l2);
        printListNode(listNode);
    }

    /**
     * 遍历打印listNode
     * @param listNode
     */
    private static void printListNode(ListNode listNode) {
        ArrayList<Integer> nums = new ArrayList<>();
        while (listNode != null) {
            nums.add(listNode.val);
            listNode = listNode.next;
        }
        System.out.println(nums);
    }

    /**
     * 通过数组组装链表
     * @param ints
     * @return
     */
    private static ListNode buildList(int[] ints) {

        ListNode listNode = null;
        if (ints.length > 0) {
            listNode = new ListNode(ints[0]);
        }
        ListNode head = listNode;
        for (int i = 1; i < ints.length; i++) {
            listNode.next = new ListNode(ints[i]);
            listNode = listNode.next;
        }
        return head;
    }


    /**
     * 合并递增链表
     * @param l1
     * @param l2
     * @return
     */
    public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {

        ListNode head = null;
        ListNode listNode = new ListNode();
        // 先判断是否有空，有空则不需要比较
        if (l1 == null && l2 == null){
            return head;
        }
        if (l1 == null && l2 != null) {
            return l2;
        }else if (l1 != null && l2 == null) {
            return l1;
        }else {

            // 逐个比较，然后放进新的链表里，这个方法时间复杂度高
            head = listNode;
            while (l1 != null) {
                if (l2 != null) {
                    if (l1.val > l2.val) {
                        listNode.val = l2.val;
                        listNode.next = new ListNode();
                        listNode = listNode.next;
                        l2 = l2.next;
                    }else {
                        listNode.val = l1.val;
                        listNode.next = new ListNode();
                        listNode = listNode.next;
                        l1 = l1.next;
                    }
                }else {
                    listNode.val = l1.val;
                    if (l1.next != null){
                        listNode.next = new ListNode();
                        listNode = listNode.next;
                    }
                    l1 = l1.next;
                }
            }
            while (l2 != null){
                listNode.val = l2.val;
                if (l2.next != null){
                    listNode.next = new ListNode();
                    listNode = listNode.next;
                }
                l2 = l2.next;
            }
        }
        return head;
    }


    // 官方答案1
    public static ListNode mergeTwoLists1(ListNode l1, ListNode l2) {

        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists1(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists1(l1, l2.next);
            return l2;
        }

        /*
        复杂度分析
        时间复杂度：O(n + m)O(n+m)，其中 nn 和 mm 分别为两个链表的长度。
                  因为每次调用递归都会去掉 l1 或者 l2 的头节点（直到至少有一个链表为空），
                  函数 mergeTwoList 至多只会递归调用每个节点一次。
                  因此，时间复杂度取决于合并后的链表长度，即 O(n+m)O(n+m)。
        空间复杂度：O(n + m)O(n+m)，其中 nn 和 mm 分别为两个链表的长度。
                  递归调用 mergeTwoLists 函数时需要消耗栈空间，栈空间的大小取决于递归调用的深度。
                  结束递归调用时 mergeTwoLists 函数最多调用 n+mn+m 次，因此空间复杂度为 O(n+m)O(n+m)。

        作者：LeetCode-Solution
        链接：https://leetcode-cn.com/problems/merge-two-sorted-lists/solution/he-bing-liang-ge-you-xu-lian-biao-by-leetcode-solu/
        来源：力扣（LeetCode）
        著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
         */

    }

    // 官方答案2
    public static ListNode mergeTwoLists2(ListNode l1, ListNode l2) {
        ListNode prehead = new ListNode(-1);

        ListNode prev = prehead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                prev.next = l1;
                l1 = l1.next;
            } else {
                prev.next = l2;
                l2 = l2.next;
            }
            prev = prev.next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;

        return prehead.next;
    }
}
